package cn.zzf.algs.note.exercise.sort;

import cn.zzf.algs.note.base.collection.v2.LinkedQueue;
import cn.zzf.algs.note.base.util.SortUtil;

/**
 * 归并两个有序的队列。编写一个静态方法，将两个有序的队列作为参数，返回一个归并后的有序队列
 * @author GaoFeng2017
 * @date 2020/7/21 11:04
 */
public class Ex_2_2_14_MergeTwoQueue {

    public static LinkedQueue<Comparable> merge(LinkedQueue<Comparable> leftElements, LinkedQueue<Comparable> rightElements) {

        // 1
        // 2
        // 3
        // 4

        // 2,1
        // 4,3

        LinkedQueue<Comparable> result = new LinkedQueue<>();

        Comparable leftElement = leftElements.dequeue();
        Comparable rightElement = rightElements.dequeue();

        while (leftElement != null || rightElement != null) {
            if (leftElement == null) {
                result.enqueue(rightElement);
                rightElement = rightElements.dequeue();
            } else if (rightElement == null) {
                result.enqueue(leftElement);
                leftElement = leftElements.dequeue();
            } else if (SortUtil.less(rightElement, leftElement)) {
                result.enqueue(rightElement);
                rightElement = rightElements.dequeue();
            } else {
                result.enqueue(leftElement);
                leftElement = leftElements.dequeue();
            }
        }

        //返回合并后队列
        return result;
    }

}